class Solution {//leetcode300——最长递增子序列
private:
    int dfs(vector<int>&nums,int pos){
        if(memory[pos]!=0) return memory[pos];
        int ret=0;
        for(int i=pos+1;i<n;i++){
            if(nums[pos]<nums[i])//剪枝操作
                ret=max(ret,dfs(nums,i)+1);
        }
        memory[pos]=ret;
        return memory[pos];
    }
public:
    int lengthOfLIS(vector<int>& nums) {
        int ret=1;
        n=nums.size();
        memory.resize(n,0);
        for(int i=0;i<n;i++){
            ret=max(ret,dfs(nums,i)+1);//dfs()返回以该节点组成的决策树子树的高度
        }
        return ret;
    }
private:
    int n;
    vector<int> memory;
};